﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Brainee.Search
{
  /// <summary>
  /// Breadth-first search selects the shallowest unexpanded node in the search tree for
  /// expansion. 
  /// </summary>
  /// <remarks>
  /// It is complete, optimal for unit step costs, and has time and space complexity of
  /// O(b^(d+l)) where b is the branching factor in the state space, and d, the depth of the 
  /// shallowest solution. The space complexity makes it impractical in most cases.
  /// </remarks>
  public class BreadthFirstStrategy : ISearchStrategy
  {
#region Fields

    private Brainee.Immutable.IQueue<ISearchState> _fringe;

#endregion
#region Strategy definition

    /// <summary>
    /// Initialize the strategy internals with the specified problem.
    /// </summary>
    /// <param name="problem">The problem to solve with this strategy.</param>
    public void Initialize (IProblem problem)
    {
      if (problem == null)
        throw new ArgumentNullException ("problem");

      _fringe = Brainee.Immutable.Queue<ISearchState>.Empty;
      _fringe = _fringe.Enqueue (new SearchState (problem.InitialState));
    }

    /// <summary>
    /// Test if there are unexplored search states.
    /// </summary>
    /// <returns>false if there is at least one state that can be explored; otherwise, true</returns>
    public bool HasUnexploredStates ()
    {
      if (_fringe == null)
        throw new InvalidOperationException ("The strategy is not correctly initialized.");

      return !_fringe.IsEmpty;
    }

    /// <summary>
    /// Get the next unexplored state.
    /// </summary>
    /// <returns>An unexplored search state</returns>
    public ISearchState NextState ()
    {
      if (_fringe == null)
        throw new InvalidOperationException ("The strategy is not correctly initialized.");

      if (_fringe.IsEmpty)
        return null;

      ISearchState next = _fringe.Peek ();
      _fringe = _fringe.Dequeue ();

      return next;
    }

    /// <summary>
    /// Expands the specified state
    /// </summary>
    /// <param name="state">The state to expand</param>
    /// <param name="problem">The problem to solve</param>
    public void Expand (ISearchState state, IProblem problem)
    {
      if (_fringe == null)
        throw new InvalidOperationException ("The strategy is not correctly initialized.");
      if (state == null)
        throw new ArgumentNullException ("state");
      if (problem == null)
        throw new ArgumentNullException ("problem");

      foreach (ActionState pair in problem.Successors (state.State))
      {
        _fringe = _fringe.Enqueue(new SearchState (
          pair.State,
          state,
          pair.Action,
          state.PathCost + problem.StepCost (state.State, pair.Action, pair.State),
          state.Depth + 1));
      }
    }

#endregion
  }
}
